import java.util.ArrayList;
import java.util.List;
public class TestBiraryTree {
    static  class TreeNode {
        public char val;
        public TreeNode Left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
        public TreeNode root; // 代表二叉树的根节点

        public  TreeNode createTree(){
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.Left = B;
            A.right = C;
            B.Left = D;
            B.right = E;
            C.Left = F;
            C.right = G;
            E.right = H;
            this.root = A;
            return root;
        }

        //前序遍历 根左右
        public void perOrder(TreeNode root){
            // 可以是递归的 也可以是非递归的
            // 但80%都是递归的
            //递归打印

            //终止条件是
            if(root == null){
                 return;
            }
            System.out.print(root.val+" ");
            perOrder(root.Left); // 开始递归左树
            perOrder(root.right);// 再开始递归右树

            // 非递归实现前序遍历
        // 非递归要在栈上完成

        // 先定义一个变量cur来记录根节点的位置
        // 因为根节点是不能改变的，所以要记录一个跑腿的
        // 让cur去走二叉树的子树，根据前序遍历，不为空的话将其放入栈中,并同时打印这个入栈的节点
        // 当继续向下走左边为空的话弹出栈顶元素 ， 定义一个变量top 记录这个弹出栈顶元素 , 并将cur指向这个栈顶元素的右边
        // 如果这时的右边也为空的话继续弹出当前的栈顶元素，再将cur指向新的栈顶元素的右边
        if(root == null){
            return;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
       while(cur != null || !stack.isEmpty()) { // 要看栈空不空。这一点是关键
           while (cur != null) {  // 这个逻辑是反过来的
               stack.push(cur); // 放入根节点
               System.out.println(cur.val + " ");
               cur = cur.Left;
           }
           TreeNode top = stack.pop();
           cur = top.right;
       }
        System.out.println();
        }

        // 前序遍历的方法2：LeetCode题
        List<Integer> ret = new ArrayList<>();
        public List<Integer> preorderTraversal(TreeNode root) {
            if(root == null){
                return ret;
            }
            System.out.print(root.val+" ");
            ret.add(root.val); //这一句报红正常
            preorderTraversal(root.Left); // 开始递归左树
            preorderTraversal(root.right);// 再开始递归右树
            return ret;
        }

         // 前序遍历的方法3：LeetCode题
        List<Integer> ret = new ArrayList<>();
        public List<Integer> preorderTraversal(TreeNode root) {
            if(root == null){
                return ret;
            }
           // System.out.print(root.val+" ");
            ret.add(root.val); //这一句报红正常
           List<Integer> leftTree =  preorderTraversal(root.Left); // 开始递归左树
           ret.addAll(leftTree);
            List<Integer> rightTree = preorderTraversal(root.right);// 再开始递归右树
            ret.addAll(rightTree);
            return ret;
        }


    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return ret;
        }
        System.out.print(root.val+" ");
        ret.add(root.val); //这一句报红正常
        preorderTraversal(root.Left); // 开始递归左树
        preorderTraversal(root.right);// 再开始递归右树
        return ret;
    }

        //中序遍历 左根右
        public void inOrder(TreeNode root){
            //终止条件是
            if(root == null){
                return;
            }
            inOrder(root.Left); // 先打印左边
            System.out.print(root.val+" "); // 再打印
            inOrder(root.right);// 再开始递归右树
        }

        // 同理中序遍历的力扣题
         List<Integer> ret = new ArrayList<>();
        public List<Integer> InorderTraversal(TreeNode root) {
            if(root == null){
                return ret;
            }
           // System.out.print(root.val+" ");
           List<Integer> leftTree =  InorderTraversal(root.Left); // 开始递归左树
           ret.addAll(leftTree);
            ret.add(root.val); //这一句报红正常
            List<Integer> rightTree = InorderTraversal(root.right);// 再开始递归右树
            ret.addAll(rightTree);
            return ret;
        }

        //后序遍历 左右根
        public void postOrder(TreeNode root){
            if(root == null){
                return;
            }
            inOrder(root.Left); // 先打印左边
            inOrder(root.right);// 再开始递归右树
            System.out.print(root.val+" "); // 再打印
        }

        // 后续遍历的力扣题同理

        //获取二叉树中节点的个数
    //时间复杂度是：O（N）
    // 空间复杂度是： O(logN) //再最好情况下（满二叉树的情况下）
   public int size(TreeNode root){
        // 子问题： 左数的节点加右树的节点再加上一个1
       if(root == null){
           return 0;
       }
       int leftSize = size(root.Left);
       int rightSize = size(root.right);
       return leftSize+rightSize+1;
    }

    public static int nodeSize;//是一个成员变量
    public void size2(TreeNode root){
        // 遍历思路： 遇到节点就加一
        if(root==null){
            return ;
        }
        nodeSize++;
        size2(root.Left);
        size2(root.right);
    }

    //获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root){
        // 一个节点的左树为空并且右树为空
        // 子问题思路：左叶子+右叶子
        if(root == null){
            return 0;
        }
        if(root.Left == null && root.right == null){
            return 1;
        }
        int leftLeaf = getLeafNodeCount(root.Left);
        int rightLeaf = getLeafNodeCount(root.right);
        return leftLeaf+rightLeaf;
    }

    public int leafSize;
    public void getLeafNodeCount1(TreeNode root) {
        if(root == null){
            return;
        }
        if(root.Left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount1(root.Left);
        getLeafNodeCount1(root.right);
    }

    //获取第k层节点的个数
    int getKLeveNodeCount(TreeNode root,int k){
       // 子问题思路
        // 求第k层就是求每棵左右子树的第k-1层
        // （将其看成两棵树，就是求左子树的第k-1层+右子树的第k-1层）
        // 再继续下分，等变成第一层的时候开始求值
        if(root==null){
            return 0;
        }
        if ( k==1){
            return 1;
        }
       int leftSize =  getKLeveNodeCount(root.Left,k-1);
       int rightSize =  getKLeveNodeCount(root.right,k-1);
       return leftSize+rightSize;
    }

    //获取二叉树的高度
    // 时间复杂度：O(N)
    // 空间复杂度是：O(树的高度)
    public int getHeight(TreeNode root){
        // 子问题思路
        // 左子树的高度和右子树的高度求最大值再加1
        if (root == null){
            return 0;
        }
        int leftHeight = getHeight(root.Left);
        int rightHeight = getHeight(root.right);
        // 求最大值
        return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight + 1);
    }

    //检测值为val的元素是否存在
      public TreeNode find(TreeNode root,int val){
            // 问题就是怎么遍历这个二叉树
          // 前中后序
          // 这里以前序遍历
          if(root==null){
              return null;
          }
          // 先看根节点是否是
          if(root.val == val){
              return root;
          }
          // 再看左子树
          TreeNode leftTree = find(root.Left,val);
          if(leftTree != null){
              return leftTree;// 说明找到了
          }
          //左子树没有了再看右子树
          TreeNode rightTree = find(root.right,val);
          if(rightTree!=null){
              return rightTree; //
          }
          return null;// 能够走到这里说明没有找到
      }


      //层序遍历
        public  void levelOrder(TreeNode root){
            //从上到下，从左到右依次遍历

            // 用非递归的方法
            // 用队列去做
            if(root == null){
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            // 先入左再入右
            // 队列不为空弹出并打印
            // 节点没有子树就不放进队列当中
            queue.offer(root);
            //队列为空就打印完了
            while (!queue.isEmpty()){
             TreeNode cur =  queue.poll();
                System.out.print(cur.val+" ");
                if(cur.Left != null){
                    queue.offer(cur.Left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }

        }



    //判断两颗树是否相同
    // 时间复杂度 O(min(m,n))
    // 空间复杂度 O(min(m,n)) //树的最大高度
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 先判断根节点是否相同
        // 如何辨别相同
        // 结构相同 值也要相同
        // 1.一个为空一个不为空 ，false
        // 2. 两个都为空 ， true
        // 3. 两个都不为空 不一定 要看值
        if(p == null && q != null || p!=null&&q == null){
            return false;   //1
        }
        // 走到这里就说明 要么都为空要么都不为空
        if(p == null && q == null){
            return true;  //1
        }

            if(p.val != q.val){
                return false;  //1
            }
            // 下面就是p q 都不为空 并且值一样
          return isSameTree(p.Left,q.Left) && isSameTree(p.right,q.right);  // O(N)
    }


    //另一棵树的子树
    // 时间复杂度：O(|s|*|t|);
    // 空间复杂度: O(max(s,t));
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 1. 判断是不是相同的树
        // 是 true
        // 不是的话 就不一定
        //2.是不是 root的左子树
        // 3. 是不是root的右子树
        // 两个都不是就不是root的子树
        // 调用上面是否相同的方法
        if(root == null || subRoot == null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.Left,subRoot)) return true;
        if(isSubtree(root.right,subRoot)) return true;
        return false;
    }

    //  翻转二叉树

    // 时间复杂度：O(N)
    // 空间复杂度：O(N)
    //给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.Left;
        root.Left = root.right;
        root.right = tmp;
        invertTree(root.Left);
        invertTree(root.right);
        return root;
    }

    // 判断一棵二叉树是否是平衡二叉树
    //一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

    // 时间复杂度是：O(N^2) // 因为求高度的时间复杂度是O(N) , 有N个求高度的

    // 空间复杂度是：O(logN)
    public boolean isBalanced(TreeNode root) {
        // 需要调用上面求高度的方法
        if(root == null){
            return true;
        }
        if(getHeight(root) == 0){
            return false;
        }
        int leftH = getHeight(root.Left);
        int rightH = getHeight(root.right);
       return Math.abs(leftH - rightH) < 2 && isBalanced(root.Left) && isBalanced(root.right);


       //那么如何用时间复杂度为O（N）来求这一道题呢
        //上面呢种写法是有重复的计算
        // 思路就是求高度的过程当中 就判断是否平衡
        // 这个方法需要直接改变求高度的方法  ： 这样方法2和方法3 的时间复杂度都是O(N)
        //方法2：

   /*     public boolean isBalanced(TreeNode root) {
            return getHeight(root) >= 0;
        }

        public int getHeight(TreeNode root){
            // 子问题思路
            // 左子树的高度和右子树的高度求最大值再加1
            if (root == null){
                return 0;
            }
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            // 求最大值
            if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1){
                return Math.max(leftHeight,rightHeight)+1;
            }else{
                return -1;
            }
        }*/

        // 方法3；
        //   public boolean isBalanced(TreeNode root) {
        //        return getHeight(root) >= 0;
        //    }
        //
        //    public int getHeight(TreeNode root){
        //        // 子问题思路
        //        // 左子树的高度和右子树的高度求最大值再加1
        //        if (root == null){
        //            return 0;
        //        }
        //        int leftHeight = getHeight(root.left);
        //        if(leftHeight < 0) return -1;
        //        int rightHeight = getHeight(root.right);
        //        if(rightHeight < 0) return -1;
        //        // 求最大值
        //       if(Math.abs(leftHeight - rightHeight) <= 1){
        //           return Math.max(leftHeight,rightHeight)+1;
        //       }else{
        //           return -1;
        //      }
    }


    // 对称二叉树
    //给你一个二叉树的根节点 root ， 检查它是否轴对称。
    public boolean isSymmetric(TreeNode root) {
        //判断整棵树是否是轴对称的，就判断这颗树的左子树和这颗树的右子树是否是对称的
        //如何判断左子树和右子树对称

        // 左子树的左树和右子树的右树
        // 左子树的右树和右子树的左树
        // 一个方法是不能够实现的，因为至少要有两个参数
        if(root == null) return true;
        return isSymmetricChild(root.Left,root.right);

    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree == null && rightTree != null || rightTree == null && leftTree != null){
            return false;
        }
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree.val != rightTree.val){
            return false;  //1
        }
        return isSymmetricChild(leftTree.Left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.Left);
    }
    // 二叉树的构建及遍历


    // 二叉树的分层遍历
    // 就是上面的层序遍历,但是有返回值，跟上面的还是不一样
    // 得确定那一层有哪一些节点
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        // 怎么知道每一层的个数呢
        // 定义一个size表示 对立中的节点个数
        // 有几个节点就代表呢一层有几个节点
        // 所以用两个while循环
        if(root == null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        // 先入左再入右
        // 队列不为空弹出并打印
        // 节点没有子树就不放进队列当中
        queue.offer(root);
        //队列为空就打印完了
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while(size!=0) {
                TreeNode cur = queue.poll();
                //System.out.print(cur.val + " ");
                tmp.add(cur.val);
                size--;
                if (cur.Left != null) {
                    queue.offer(cur.Left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }

    // 输出一棵二叉树的左视图
    //二叉树的构建和遍历
    // 给一个前序遍历的字符串来创建一个二叉树
    // 先去创建根节点


/*    static  class TreeNode {
        public char val;
        public TreeNode Left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }*/
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
        }
    }
    //开始创建二叉树
    public static int i = 0;
    public static TreeNode createTree(String str){
        // 用先序遍历来创建二叉树
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.Left = createTree(str);
            root.right = createTree(str);

        }else{
            i++;
        }
        return root;
    }

    //用中序遍历来进行打印
    public static void Inorder(TreeNode root){
        if(root == null) return;
        Inorder(root.Left);
        System.out.print(root.val+" ");
        Inorder(root.right);
    }



    //给定一个二叉树。找到该书中两个指定节点的最近公共祖先

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 有一下几种情况
        // 要么在根的左右两边
        // 要么都在根的左边或者右边
        // 要么这两个节点的其中一个节点就是公共祖先

        // 如果root是一颗空树那就不存在公共祖先
        if(root == null){
            return null;
        }
        //再判断根节点是不是这两个节点的其中一个如果使得话那就返回根节点
        if(root == p || root == q){
            return root;
        }
        // 在讨论如果两者都不为空的话那就直接返回根节点
        //看看能不能在左右两边找到节点
        TreeNode leftRet = lowestCommonAncestor(root.Left, p, q);
        TreeNode rightRet = lowestCommonAncestor(root.right, p, q);

        if(leftRet!=null&&rightRet!=null){
            return root;
        }
        // 再讨论两个节点在同一位置的时候
        else if (leftRet != null) {
            return leftRet;
        }else if(rightRet != null){
            return rightRet;
        }
        return null;
    }


    // 方法二
    //  求相交节点
    // 如何把从根节点到指定节点，路径上所有的节点找到，放到栈里面
    // 你怎么知道当前这个节点弹出去

    // 找到从根节点到指定节点node路径上的所有节点，存放到栈当中

    // 这个时间复杂度是树的高度

    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack){
        if(root == null || node == null){
            return false;
        }
        stack.push(root); // 先放根节点
        //每次放完之后要检查
        if(root == node){
            return true;
        }
        // 先往左边找
        boolean ret1 =  getPath(root.Left,node,stack);
        if(ret1){
            return true;
        }
        boolean ret2 =  getPath(root.right,node,stack);
        if(ret2){
            return true;
        }
        // 左右都为false 没找到的话要先弹出压进去的栈
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        // 第一步 两个栈当中存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);  // 存储到p的路径
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2); // 存储到q的路经的栈

        // 第二步 判断栈的大小
        int size1 = stack1.size();
        int size2 = stack2.size();

        if (size1 > size2){
            int size = size1 - size2;
            while (size!=0){
                stack1.pop();
                size--;
            }
        }else {
            int size = size2 - size1;
            while (size!=0){
                stack2.pop();
                size--;
            }
        }
        // 这时候栈里面数据的个数是一样的
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek() != stack2.peek()){
                stack1.pop();
                stack2.pop();
            }else{
                return stack1.peek();
            }
        }
        return null;
    }



    // 根据一棵树的前序遍历和中序遍历构造二叉树

    // 步骤 根据前序遍历找到根
    // 再根据中序遍历找到根的位置. 记作ri

    public int j = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       return buildChild(preorder,inorder,0,inorder.length-1);
    }
    public TreeNode buildChild(int[] preorder, int[] inorder , int inBegin , int inEnd) {
        if(inBegin > inEnd){
            return null; // 说明没有子树了
        }
        TreeNode root = new TreeNode(preorder[j]);

        int rootIndex = findex(inorder , inBegin , inEnd,preorder[j]);// 在中序遍历中找到这个节点
        j++;
        root.Left = buildChild(preorder,inorder,inBegin,rootIndex-1);
        root.right = buildChild(preorder,inorder,rootIndex+1,inEnd);

        return root;
    }

    public int findex(int[] inorder , int inBegin , int inEnd , int key){
        for (int i = inBegin; i <= inEnd; i++) {
            if(inorder[i] == key){
                return i;
            }
        }
        return -1; // 表示找不到
    }
    // 用中序遍历和后续遍历 来找一个二叉树
    // 后序遍历等确定什么，能确定一个根
    // 所以要在中序遍历中找到根所在的位置 记作ri
    // 再记录 InBegin 和 InEnd
    // 那么是先创建又树还是先创建左树呢
    // 先创建右树  （把根创建好之后 再创建右树）

    // class Solution {
    //        public int j = 0;
    //        public TreeNode buildTree(int[] inorder, int[] postorder) {
    //        j = postorder.length - 1;
    //        return buildChild(postorder,inorder,0,inorder.length-1);
    //    }
    //    public TreeNode buildChild(int[] postorder, int[] inorder , int inBegin , int inEnd) {
    //        if(inBegin > inEnd){
    //            return null; // 说明没有子树了
    //        }
    //        TreeNode root = new TreeNode(postorder[j]);
    //        int rootIndex = findex(inorder , inBegin , inEnd,postorder[j]);// 在中序遍历中找到这个preorder[j]节点作为根节点
    //        j--;
    //         root.right = buildChild(postorder,inorder,rootIndex+1,inEnd);
    //        root.left = buildChild(postorder,inorder,inBegin,rootIndex-1);
    //        return root;
    //    }
    //
    //    public int findex(int[] inorder , int inBegin , int inEnd , int key){
    //        for (int i = inBegin; i <= inEnd; i++) {
    //            if(inorder[i] == key){
    //                return i;
    //            }
    //        }
    //        return -1; // 表示找不到
    //    }
    //}


    // 二叉树创建字符串
    //用前序遍历的方式
    //空节点使用一对空括号对 "()" 表示，

    // 这棵树不为空就加一个"("这棵树走完了就加一个")"
    // 如果是左边为空右边不为空直接加一个"()"再走右边
    public String tree2str(TreeNode root) {
        if(root == null){
            return null;
        }
        StringBuilder stringbuilder = new StringBuilder();
        tree2str2(root,stringbuilder);
        return stringbuilder.toString();
    }
    public void tree2str2(TreeNode t,StringBuilder stringbuilder) {
        if(t == null){
            return;
        }
        // 先把根节点加上
        stringbuilder.append(t.val);
        // 然后开始看左树
        if(t.Left != null){
            stringbuilder.append("(");
            tree2str2(t.Left,stringbuilder);
            stringbuilder.append(")");
        }else{
            if(t.right != null){
                stringbuilder.append("()");
            }else{
                return;
            }
        }
        // 最后再看右树
        if(t.right == null){
            return;
        }else{
            stringbuilder.append("(");
            tree2str2(t.right,stringbuilder);
            stringbuilder.append(")");
        }
    }

    // 判断一颗二叉树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        // 要用到队列
        // 队列里面有空且有不为空的话就能证明不是完全二叉树

        // 如果是完全二叉树的话队列里面全是null
        if(root == null){
            return true; // 空树可以表示为一颗完全二叉树
        }
        Queue<TreeNode> queue = new LinkedList<>();
        // 每次从队列中取出一个节点

        //这个节点分为两种情况
        // 要么为空要么不为空

        // 开始判断队列中剩余的元素
        // 把左子树和右子树带进来
        queue.offer(root); // 先把根节点放进去

        while(!queue.isEmpty())  { // 当队列不为空的时候进入循环
                TreeNode cur = queue.poll();
                if (cur != null) {
                    queue.offer(cur.Left);
                    queue.offer(cur.right);
                }else{
                    break;
                }
        }
        while(!queue.isEmpty()){
            TreeNode tmp = queue.poll();
            if(tmp!=null){     // 上面的循环结束后 说明第一个对头为空了，接下来判断剩余队列的节点里面有没有空置
                return false;  //这时候从队列里面接收一个值 ， 如果没有空值就证明不是完全二叉树
            }
        }
        return true; // 走到这里说明队列已经走完了 ， 队列已经弹完了
    }




    // 用非递归的方式实现二叉树的前中后序遍历

    // 非递归方式的中序遍历
    public void inOrderNor(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur != null || !stack.isEmpty()) { // 要看栈空不空。这一点是关键
            while (cur != null) {  // 这个逻辑是反过来的
                stack.push(cur); // 放入根节点
               // 中序遍历这里不着急打印
                cur = cur.Left;
            }
            TreeNode top = stack.pop();
            System.out.println(top.val + " ");
            cur = top.right;
        }
        System.out.println();
    }

        // 非递归的方法写后序遍历 (左 右 根)
    public void postorder(TreeNode root){
        // 后序遍历就不能直接pop了
        if(root == null){
            return;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur != null || !stack.isEmpty()) { // 要看栈空不空。这一点是关键
            while (cur != null) {  // 这个逻辑是反过来的
                stack.push(cur); // 放入根节点
                // 中序遍历这里不着急打印
                cur = cur.Left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev/*被打印过*/) {  // 如果这个节点的右边为空那就直接打印这个节点
                System.out.println(top.val+" ");
                // 打印完之后再将这个节点弹出去
                stack.pop();  // 只写到这里的话会陷入死循环无限打印一个节点、少了一个条件，写到这是表示，如果这个节点的右边已经被打印过了还能继续被打印
                prev = top;
            }else{
                cur = top.right; // 不为空的话就让这个节点向右走
            }
        }
    }

    }
